#ifndef cathlibcpp_assocbase_H
#define cathlibcpp_assocbase_H

// File:       assocbase.h
// Author:     (c) Miles Sabin, 1996
// Purpose:    red-black tree for map and set implementation


#ifndef included_stddef_H
#define included_stddef_H
#include <stddef.h>                  // for size_t
#endif

#ifndef cathlibcpp_bool_H
#include "bool.h"
#endif

#ifndef cathlibcpp_config_H
#include "config.h"
#endif

#ifndef cathlibcpp_utility_H
#include "utility.h"                 // for pair<T1, T2>
#endif


class HoistBinaryPredicateProtocol;
class HoistConstructorDestructorProtocol;


struct assoc_base_node
{
  assoc_base_node* left;
  assoc_base_node* right;
  assoc_base_node* parent;
  int colour;
};


class assoc_base
{
  friend bool operator==(assoc_base const& rhs, assoc_base const& lhs);
  friend bool operator< (assoc_base const& rhs, assoc_base const& lhs);

  public:

    // CFront chokes on typedefs here.

#   define iterator                  assoc_base_node*
#   define const_iterator            assoc_base_node const*
#   define size_type                 size_t
#   define difference_type           ptrdiff_t

    // constructors
    assoc_base
      (HoistConstructorDestructorProtocol const& key_ctdt, HoistConstructorDestructorProtocol const* mapped_ctdt, HoistBinaryPredicateProtocol* key_cmp,
        bool allow_duplicates);
    assoc_base
      (HoistConstructorDestructorProtocol const& key_ctdt, HoistConstructorDestructorProtocol const* mapped_ctdt, HoistBinaryPredicateProtocol* key_cmp,
       bool allow_duplicates, const_iterator first, const_iterator last);
    assoc_base
      (HoistConstructorDestructorProtocol const& key_ctdt, HoistConstructorDestructorProtocol const* mapped_ctdt, HoistBinaryPredicateProtocol* key_cmp,
       bool allow_duplicates, void const* first, void const* last);
    assoc_base(assoc_base const& rhs, HoistBinaryPredicateProtocol* key_cmp);
    ~assoc_base();

    // accessors
    const_iterator begin() const;
    const_iterator end() const;

    bool empty() const;
    size_type size() const;
    size_type max_size() const;

    const_iterator find(void const* x) const;

    size_type count(void const* x) const;

    const_iterator lower_bound(void const* x) const;
    const_iterator upper_bound(void const* x) const;
    pair<const_iterator, const_iterator> equal_range(void const* x) const;

    // mutators
    assoc_base& operator=(assoc_base const& rhs);

    iterator begin();
    iterator end();

    pair<iterator, bool> insert(void const* x);
    iterator insert(iterator hint, void const* x);
    void insert(const_iterator first, const_iterator last);
    void insert(void const* first, void const* last);

    void erase(iterator position);
    size_type erase(void const* x);
    void erase(iterator first, iterator last);

    void swap(assoc_base& x);

    void clear();

    iterator find(void const* x);

    iterator lower_bound(void const* x);
    iterator upper_bound(void const* x);
    pair<iterator, iterator> equal_range(void const* x);

    const_iterator successor(const_iterator x) const;
    const_iterator predecessor(const_iterator x) const;

    iterator successor(iterator x);
    iterator predecessor(iterator x);

    bool is_equal
      (HoistBinaryPredicateProtocol const& key_comparator, HoistBinaryPredicateProtocol const* mapped_comparator,
       assoc_base const& rhs) const;
    bool is_less_than
      (HoistBinaryPredicateProtocol const& key_comparator, HoistBinaryPredicateProtocol const* mapped_comparator,
       assoc_base const& rhs) const;

  private:

    enum colour_type { red, black };

    // accessors
    const_iterator root() const;
    const_iterator minimum() const;
    const_iterator maximum() const;

    const_iterator minimum(const_iterator x) const;
    const_iterator maximum(const_iterator x) const;

    // mutators
    void init();

    assoc_base_node* new_node(void const* x);
    void delete_node(assoc_base_node* n);

    iterator& root();
    iterator& minimum();
    iterator& maximum();

    iterator minimum(iterator x);
    iterator maximum(iterator x);

    iterator assign_aux(const_iterator from, const_iterator from_nil, iterator parent);

    void left_rotate(iterator x);
    void right_rotate(iterator x);

    void insert_fixup(iterator x);
    iterator insert_aux(iterator i, iterator p, void const* x);

    void delete_fixup(iterator x);

    void clear_aux(iterator x);

    bool value_equal
      (HoistBinaryPredicateProtocol const& key_comparator, HoistBinaryPredicateProtocol const* mapped_comparator,
       assoc_base_node const* x, assoc_base_node const* y) const;
    bool value_less
      (HoistBinaryPredicateProtocol const& key_comparator, HoistBinaryPredicateProtocol const* mapped_comparator,
       assoc_base_node const* x, assoc_base_node const* y) const;

    // not implemented
    assoc_base(assoc_base const& rhs);

    assoc_base_node* control_node_;
    assoc_base_node* nil_;
    size_type size_;
    bool allow_duplicates_;
    HoistConstructorDestructorProtocol const& key_ctdt_;
    HoistConstructorDestructorProtocol const* mapped_ctdt_;
    size_type value_size_;
    size_type mapped_offset_;
    HoistBinaryPredicateProtocol* key_cmp_;

#   undef iterator
#   undef const_iterator
#   undef size_type
#   undef difference_type
};

#endif
